//
// Created by ct on 2021/11/3.
//

#ifndef ALGOANDSTRUCT_BTREE_H
#define ALGOANDSTRUCT_BTREE_H

#include <memory>
#include <stack>
#include <vector>
#include <iostream>
#include <queue>

using std::vector;
using std::stack;
using std::queue;

struct node {
    using sp_node = std::shared_ptr<node>;
    int val;
    sp_node left;
    sp_node right;

    // explicit node() =default;
    explicit node(int v) : val(v), left(nullptr), right(nullptr) {}
};


//struct TreeNode {
//    int val;
//    TreeNode *left;
//    TreeNode *right;
//
//    TreeNode() : val(0), left(nullptr), right(nullptr) {}
//
//    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//
//    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
//};


class btree {

public:
    /*
    *                 1
    *      2                   3
    *  4      5             6     7
    *    8
    *  9
    */
    static node::sp_node creat_tree() {

        node::sp_node node1 = std::make_shared<node>(1);
        node::sp_node node2 = std::make_shared<node>(2);
        node::sp_node node3 = std::make_shared<node>(3);
        node::sp_node node4 = std::make_shared<node>(4);
        node::sp_node node5 = std::make_shared<node>(5);
        node::sp_node node6 = std::make_shared<node>(6);
        node::sp_node node7 = std::make_shared<node>(7);
        node::sp_node node8 = std::make_shared<node>(8);
        node::sp_node node9 = std::make_shared<node>(9);

        node1->left = node2;
        node1->right = node3;

        node2->left = node4;
        node2->right = node5;

        node3->left = node6;
        node3->right = node7;

        node4->right = node8;

        node8->left = node9;

        return node1;
    }

    static vector<int> per_order(node::sp_node root) {
        vector<int> vc;
        stack<node::sp_node> st;
        while (root != nullptr || !st.empty()) {
            while (root != nullptr) {
                vc.push_back(root->val);
                st.push(root);
                root = root->left;
            }
            root = st.top();
            root = root->right;
            st.pop();
        }
        return vc;
    }

    static vector<int> in_order(node::sp_node root) {
        vector<int> vc;
        stack<node::sp_node> st;
        while (root != nullptr || !st.empty()) {
            while (root != nullptr) {
                st.push(root);
                root = root->left;
            }
            root = st.top();
            vc.push_back(root->val);
            root = root->right;
            st.pop();
        }
        return vc;
    }

    static vector<int> post_order(node::sp_node root) {
        vector<int> vc;
        stack<node::sp_node> st;
        node::sp_node p_last_visit;

        while (root != nullptr) {
            st.push(root);
            root = root->left;
        }

        while (!st.empty()) {
            root = st.top();
            st.pop();
            if (root->right == nullptr || p_last_visit == root->right) {
                vc.push_back(root->val);
                p_last_visit = root;
            } else {
                st.push(root);
                root = root->right;
                while (root != nullptr) {
                    st.push(root);
                    root = root->left;
                }
            }
        }

        return vc;
    }

    static void per_order_witch(const node::sp_node &root, vector<int> &vc) {
        if (root == nullptr) {
            return;
        }
        vc.push_back(root->val);
        per_order_witch(root->left, vc);
        // vc.push_back(root->val); /* 中序遍历*/
        per_order_witch(root->right, vc);
        // vc.push_back(root->val);/* 后序遍历*/
    }

    using TreeNode = node::sp_node;

    static vector<vector<int>> levelOrder(const TreeNode &root) {
        vector<vector<int>> ans;
        queue<TreeNode> que;
        if (root != nullptr)que.push(root);
        while (!que.empty()) {
            vector<int> vec;

            int size =(int) que.size();
            for (int i = 0; i < size; ++i) {
                TreeNode node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left != nullptr) que.push(node->left);
                if (node->right != nullptr) que.push(node->right);
            }
            ans.push_back(vec);
        }
        return ans;
    }
};


#endif //ALGOANDSTRUCT_BTREE_H
